package com.jat.algorithms.sort;

import java.util.Arrays;

/**
 * @author jatchen
 * @description: 归并排序
 * @date 2021/9/288:45 PM
 */
public class MergeSort {

    public static void main(String[] args) {
        int []arr = {9,8,7,6,5,4,3,2,1};

        mergeSoft(arr);
        System.out.println(Arrays.toString(arr));
    }

    /***
     * 非原地排序
     * 思路：
     * 还用递归，拆分子序列
     * 子序列排好序好再合并，最终合并完成就排好序了
     * 利用另外一个长度一样的数组，两个指针分别指向两个子序列的开头元素，遍历从小到大放置到备用数组中
     * @param array
     */
    private static void mergeSoft(int[] array){
        int[] temp = new int[array.length];//排序前，开辟一块空间
        sort(array,0,array.length-1,temp);
    }

    private static void sort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序，使左边子数组有序
            sort(arr,mid+1,right,temp);//右边归并排序，使右边子数组有序
            merge(arr,left,mid,right,temp);//将两个有序子数组合并
        }
    }

    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;//左子数组指针
        int j = mid+1;//右子数组指针
        int t = 0 ;//临时数组指针
        while (i<=mid && j<=right){
            if (arr[i]<=arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while (i<=mid){//将左数组剩余元素放进temp中
            temp[t++] = arr[i++];
        }
        while (j<=right){//右子数组剩余元素填充回temp
            temp[t++] = arr[j++];
        }

        t = 0;
        //将temp元素copy回原数组
        while (left<=right){
            arr[left++] = temp[t++];
        }
    }
}
